Grover's Algorithm

• Can speed up an unstructured search problem quadratically

Unstructured Search

• Classical computation - average N/2
• Grover's amplitude amplification - square root of N

Amplitude Amplification

1. Starts out in uniform superposition |s⟩
2. Apply oracle reflection Uf to state |s⟩
3. Apply additional reflection Us about the state |s⟩ (Us = 2|s⟩⟨s| − 1)
   Then go to step 2 to repeat application, after t steps we will be in the state |ψt⟩